package com.learn.algorithm.stack;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.EmptyStackException;

public class MyStack<T> implements IStack<T> {
    public MyStack() {
        elementData = new Object[5];
    }

    /**
     * 扩容后增长大小
     */
    private int capacityIncrement = 5;
    /**
     * 栈的最大大小
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    /**
     * 栈数据数组
     */
    protected Object[] elementData;
    /**
     * 栈的长度
     */
    protected int elementCount;
    protected transient int modCount = 0;


    @Override
    public synchronized void push(T Item) {
        this.modCount++;
        if ((elementCount + 1 - this.elementData.length) > 0) {
            this.grow(elementCount + 1);
        }
        this.elementData[this.elementCount++] = (Object) Item;
    }

    @Override
    public synchronized T pop() {
        T obj;
        int len = size();
        obj = peek();
        elementCount--;
        elementData[elementCount] = null;
        return obj;
    }

    @Override
    public synchronized T peek() {
        int len = size();
        if (len == 0) {
            throw new EmptyStackException();
        }
        return (T) this.elementData[len - 1];
    }

    /**
     * 判定栈是否为空
     *
     * @return
     */
    public synchronized boolean isEmpty() {
        return elementCount == 0;
    }

    /**
     * 返回栈的大小
     *
     * @return
     */
    public synchronized int size() {
        return this.elementCount;
    }

    /**
     * 查找栈中是否存在元素obj
     *
     * @param obj
     * @return
     */
    public synchronized int search(T obj) {
        int index = size() - 1;
        if (obj == null) {
            for (int i = index; i >= 0; i--) {
                if (elementData[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = index; i >= 0; i--) {
                if (obj.equals(elementData[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

    private synchronized void removeElementAt(int index) {
        this.modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + ">=" + elementCount);
        } else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null;
    }

    /**
     * 数组扩容
     *
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = this.elementData.length;
        int newCapacity = oldCapacity + (this.capacityIncrement);
        if (newCapacity > minCapacity) {
            newCapacity = minCapacity;
        }
        if (newCapacity > MAX_ARRAY_SIZE) {
            throw new OutOfMemoryError();
        }
        this.elementData = Arrays.copyOf(this.elementData, newCapacity);
    }
}
